﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SortAlgorithm
{
    class Program
    {
        private  static int[] data = new int[] { 12, 43, 2, 34, 87, 54, 32, 16, 67, 99,49 };
        static void Main(string[] args)
        {
            HeapSort(data.Length);
            //QuickSort(0, data.Length-1);
            //MergeSort(0, data.Length);
            //RadixSort();
            //DoubleBubbleSort();
            //SelectionSort();
            //InsertSortStraight();
           // InsertSortShell();
            PrintData();
     
            Console.Read();
        }

        private static void PrintData()
        {
            for (int i = 0; i < data.Length; i++)
            {
                Console.Write(data[i] + ",");
            }
        }
        #region 交换排序
        #region 冒泡排序
        //冒泡排序  气泡一样由下往上 从最后一个依次跟之前的比较
        public static void BubbleSort()
        {
            for(int i=1;i<data.Length-1;i++)
            {
                for(int j=data.Length-1;j>=i;j--)
                {
                    if(data[j]<data[j-1])
                    {
                        int temp = data[j];
                        data[j] = data[j-1];
                        data[j - 1] = temp;
                    }
                }
                Console.WriteLine("第" + i + "次");
                PrintData();
            }
        
        }
        //双向冒泡排序
        public static void DoubleBubbleSort()
        {
            int left, right,l,r,i=0;
            int length = data.Length;
            left = 0;
            right = length - 1;
            while (left < right)
            {
                l = left + 1;
                r = right - 1;
                for (int j = left; j < right; j++)
                {
                    if (data[j] > data[j + 1])
                    {
                        int temp = data[j];
                        data[j] = data[j + 1];
                        data[j + 1] = temp;
                        r = j;
                    }
                }
                right = r;
                for (int j = right; j > left; j--)
                {
                    if (data[j] < data[j - 1])
                    {
                        int temp = data[j];
                        data[j] = data[j - 1];
                        data[j - 1] = temp;
                        l = j;

                    }
                }
                left = l;
                Console.WriteLine("第"+i+++"次排序结果");
                PrintData();
            }
        }
        #endregion

        #region 快速排序
        public static void QuickSort(int left,int right)
        {
        
            if (left < right)
            {
                int middle = data[(left + right) / 2];
                int i = left - 1;
                int j = right + 1;
                while (true)
                {
                    while (data[++i] < middle && i < right) ;
                    while (data[--j] > middle && j > 0) ;
                    if (i >= j)
                        break;
                    int number = data[i];
                    data[i] = data[j];
                    data[j] = number;
                }
                QuickSort(left, i - 1);
                QuickSort(j + 1, right);
            }
        }
        #endregion

        #endregion

        #region 选择排序

        #region 简单选择排序
        //选择排序  选择排序通过冒泡排序发展而来，区别就是选择排序每次比较后记录的是下标，比较完成后才移动依次
        //而冒泡排序则没比较依次就移动依次数组
        public static void SelectionSort()
        {
            int min, temp;
            for (int i = 0; i < data.Length; i++)
            {
                //记录下标
                min = i;
                for (int j = i + 1; j < data.Length; j++)
                {
                    if (data[j] < data[min])
                    {
                        min = j;
                      
                    }
               
                }
                temp = data[i];
                data[i] = data[min];
                data[min] = temp;
                  
            }
        }
        #endregion

        #region 堆排序

        public static void HeapSort(int top)
        {
            List<int> topNode = new List<int>();
            for (int i = data.Length / 2 - 1; i >= 0; i--)
            {
                HeapAdjust(i,data.Length);
            }
            for (int i = data.Length - 1; i > data.Length - top; i--)
            {
                int temp = data[0];
                data[0] = data[i];
                data[i] = temp;
                HeapAdjust(0,i);
            }
        }

        private static void HeapAdjust(int parent, int length)
        {
            int temp = data[parent];
            int child = parent * 2 + 1;
            while (child < length)
            {
                if (child + 1 < length && data[child] < data[child + 1])
                {
                    child++;
                }
                if (temp >= data[child])
                {
                    break;
                }
                data[parent] = data[child];
                parent = child;
                child = 2 * parent + 1;
            }
            data[parent] = temp;
        }
        #endregion

        #endregion

        #region 插入排序

        #region 直接插入
        //插入排序--直接插入
        public static void InsertSortStraight()
        {
            for (int i = 1; i < data.Length; i++)
            {
                int temp = data[i];
                if (temp < data[i - 1])
                {
                    for (int j = 0; j < i; j++)
                    {
                        if (temp < data[j])
                        {
                            temp = data[j];
                            data[j] = data[i];
                            data[i] = temp;
                        }
                    }
                }
            }
        }

        //插入排序 --直接插入1
             public static void InsertSortStraight(int[] list)
            {
                for (int i = 1; i < list.Length; ++i)
                {
                    int t = list[i];
                    int j = i;
                    while ((j > 0) && (list[j - 1] > t))
                    {
                        list[j] = list[j - 1];
                        --j;
                    }
                    list[j] = t;
                }

            }
        #endregion

        #region 希尔排序
             //插入排序--希尔排序
        public static void InsertSortShell()
        {
            int length = data.Length;
            for (int h = length / 2; h > 0; h = h / 2)
            {
                for (int i = h; i < length; i++)
                {
                    int temp = data[i];
                    if (temp < data[i - h])
                    {
                        for (int j = 0; j < i; j += h)
                        {
                            if (temp < data[j])
                            {
                                temp = data[j];
                                data[j] = data[i];
                                data[i] = temp;
                            }
                        }
                    }
                }
            }
 
        }
             #endregion


        #endregion

        #region 基数排序
        //基数排序  桶排序 箱排序

        public static void RadixSort()
        {
            //桶内第一维长度
            int x = 10;
            //桶内第二维长度
            int y = 100;
            for (int i = 0; i < x; i++)
            {
                int[,] bucket = new int[x, y];
                foreach (int item in data)
                {
                    int temp = (item / (int)Math.Pow(10, i)) % 10;
                    for (int l = 0; l < y; l++)
                    {
                        if (bucket[temp, l] == 0)
                        {
                            bucket[temp, l] = item;
                            break;
                        }
                    }
                }
                for (int o = 0, n = 0; n < x; n++)
                {
                    for (int m = 0; m < y; m++)
                    {
                        if (bucket[n, m] == 0) continue;
                        data[o++] = bucket[n, m];
                    }
                }
            }
        }
        #endregion

        #region 归并排序
        //归并排序
        public static void MergeSort(int first,int last)
        {
           
            if (first + 1 < last)
            {
                int mid = (first + last) / 2;
                MergeSort(first, mid);
                MergeSort(mid, last);
                Merger(first, mid, last);
            }
        }
        private static void Merger(int first, int mid, int last)
        {
            Queue<int> tempV = new Queue<int>();
            int indexA, indexB;
            indexA = first;
            indexB = mid;
            while (indexA < mid && indexB < last)
            {
                if (data[indexA] < data[indexB])
                {
                    tempV.Enqueue(data[indexA]);
                    indexA++;
                }
                else
                {
                    tempV.Enqueue(data[indexB]);
                    indexB++;
                }
            }
            while (indexA < mid)
            {
                tempV.Enqueue(data[indexA]);
                indexA++;
            }
            while (indexB < last)
            {
                tempV.Enqueue(data[indexB]);
                indexB++;
            }
            int index = 0;
            while (tempV.Count > 0)
            {
                data[first + index] = tempV.Dequeue();
                index++;
            }
        }
        #endregion


    }
}
